package DynamicPlan;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Bag {

//    public static void main(String[] args) {
////        int[] weights = {1, 3, 4};
////        int[] values = {15,25,30};
////        int i = Bag.calBag(weights, values, 6);
////        System.out.println(i);
////        int[] ints = {23,2,6,4,7};
////        Bag bag = new Bag();
////        boolean b = bag.checkSubarraySum(ints, 6);
////        System.out.println(b);
//        Bag bag = new Bag();
//        int[] ints = {474,83,404,3};
//        int i = bag.coinChange(ints, 264);
//        System.out.println(i);
//    }


    //0 1 背包问题
    //有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
    //
    //这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。
    //
    //这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？
    //
    //每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。
    public static int calBag(int[] weights, int[] values, int weight) {
        int[][] dp = new int[values.length][weight + 1];
        // 正序遍历
        for (int j = weights[0]; j <= weight; j++) {
            dp[0][j] = values[0];
        }
        for (int i = 1; i < weights.length; i++) {
            dp[i][0] = 0;
            for (int j = 1; j <= weight; j++) {
                if(j < weights[i]){
                    //因为加的是上一次物品的，所以不存在重复选择同一物品
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i]);
                }
            }
        }
        return dp[weights.length-1][weight];
    }


    //一维数组解决0,1背包问题,倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
    public static int calBagOneWay(int[] weights, int[] values, int weight) {
        int[] dp = new int[weight + 1];
        for (int j = weights[0]; j <= weight; j++) {
            dp[j] = values[0];
        }
        for (int i = 1; i < weights.length; i++) {
            for (int j = weight; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]);
            }
        }
        return dp[weight];
    }

    //完全背包问题，可以选无数个系统的样品
    //有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大
    public static int calBagComplete(int[] weights, int[] values, int weight) {
        int[] dp = new int[weight + 1];
        for (int j = weights[0]; j <= weight; j++) {
            dp[j] = values[j] + dp[j-weight];
        }
        for (int i = 1; i < weights.length; i++) {
            for (int j = weights[i]; j <= weight; j++) {

            }
        }
        return 0;
    }

    //给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：
    //
    //一个 好的子数组 是：
    //
    //长度 至少为 2 ，且
    //子数组元素总和为 k 的倍数。
    //注意：
    //
    //子数组 是数组中 连续 的部分。
    //如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数
    public boolean checkSubarraySum(int[] nums, int k) {
        if(nums.length <= 1){
            return false;
        }
        int[] qianZhui = new int[nums.length];
        HashSet<Integer> integers = new HashSet<>();
        int sum = 0;
        qianZhui[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            qianZhui[i] = nums[i] + qianZhui[i - 1];
            sum += nums[i];
            if(qianZhui[i] % k == 0){
                return true;
            }
        }
        for(int i = qianZhui.length - 1; i > 1; i--){
            for(int j = 0; j <= i -2; j++){
                if((qianZhui[i] - qianZhui[j]) % k == 0){
                    return true;
                }
            }
        }
        return false;
    }

    //给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
    //
    //计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
    //
    //你可以认为每种硬币的数量是无限的
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for(int i = 1; i <= amount; i++){
            dp[i] = -1;
        }
        Arrays.sort(coins);
        for(int i = coins[0]; i < amount + 1; i++){
            int min = Integer.MAX_VALUE;
            for(int coin : coins){
                if(i >= coin){
                    if(dp[i - coin] == -1){
                        continue;
                    }
                    min = Math.min(min,dp[i-coin] + 1);
                }
            }
            if(min != Integer.MAX_VALUE){
                dp[i] = min;
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        Bag bag = new Bag();
        bag.maxProfit(new int[]{7,1,5,3,6,4});
    }

    //给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
    //
    //你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    //
    //返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0
    public int maxProfit(int[] prices) {
        int[] maxPrices = new int[prices.length];
        maxPrices[prices.length - 1] = prices[prices.length - 1];
        for(int i = maxPrices.length - 2; i >= 0; i--){
            maxPrices[i] = Math.max(maxPrices[i + 1],prices[i]);
        }
        int max = -1;
        for(int i = 0; i < prices.length; i++){
            max = Math.max(max,maxPrices[i] - prices[i]);
        }
        return max;
    }

    public int maxProfitByDp(int[] prices) {
        int cost = Integer.MAX_VALUE;
        int profit = Integer.MIN_VALUE;
        for (int price : prices) {
            cost = Math.min(cost,price);
            profit = Math.max(profit,price - cost);
        }
        return profit;
    }
}
